#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 70. 爬楼梯
// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
// 输入：n = 2
// 输出：2
// 解释：有两种方法可以爬到楼顶。
// 1. 1 阶 + 1 阶
// 2. 2 阶

// 动态规划
class Solution {
public:
    int climbStairs(int n) {
        assert(n > 0);

        vector<int> memo(n+1, -1);
        memo[0] = 1;
        memo[1] = 1;
        for(int i = 2; i <= n; i++)
            memo[i] = memo[i - 1] + memo[i - 2];

        return memo[n];
    }
};

int main() {
    cout << Solution().climbStairs(10) << endl; // 89
    return 0;
}
